#include <iostream>
#include <vector>
#include <deque>

using namespace std;

class Solution {
public:
    int countPartitions(vector<int>& nums, int k){
        const int MOD = 1e9 + 7;
        int n = nums.size();
        deque<int> min_q, max_q;    // 双端队列，存储最大值、最小值队列
        vector<int> f(n + 1);
        f[0] = 1;
        long long sum_f = 0;
        int left = 0;

        for(int i = 0; i < n; ++i){
            int x = nums[i];

            // 入
            sum_f += f[i];
            while(!min_q.empty() && x <= nums[min_q.back()])
                min_q.pop_back();
            min_q.push_back(i);

            while(!max_q.empty() && x >= nums[max_q.back()])
                max_q.pop_back();
            max_q.push_back(i);

            // 出
            while(nums[max_q.front()] - nums[min_q.front()] > k){
                sum_f -= f[left];
                left++;
                if(min_q.front() < left) min_q.pop_front();
                if(max_q.front() < left) max_q.pop_front();
            }
            f[i + 1] = sum_f % MOD;
        }
        return f[n];
    }
};

int main(){
    vector<int> nums = {3,3,4};
    Solution sol;
    cout << sol.countPartitions(nums, 0) << endl;
}   